#include <ctime>
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

class LRUCache{
public:
    LRUCache(int capacity)
    :_capacity(capacity)
    {
        cout << "null" << " ";
    }

    void put(int key,int val){
        auto it = _key_it.find(key);
        if(it != _key_it.end()){
            //找到了
            it->second->second = val; //变更list中的val
            key_val_list.splice(key_val_list.begin(),key_val_list,it->second);//将值放到链表头部
            
        }else{
            //没找到
            key_val_list.push_front(pair<int,int>(key,val)); //插入链表头部
            _key_it[key] = key_val_list.begin();
            if(key_val_list.size() > _capacity){
                int last_key = key_val_list.back().first;
                key_val_list.pop_back(); //超出容量上限，将表尾删除
                _key_it.erase(last_key); //从map中删除
            }
        }
        cout << "null" << " ";
    }
    void display(){
        for(auto &i : key_val_list){
            cout <<'[' <<i.first <<','<< i.second<<"] ";
        }
        cout<<endl;
    }

    int get(int key){
        auto it = _key_it.find(key);
        if(it != _key_it.end()){
            key_val_list.splice(key_val_list.begin(),key_val_list,it->second);//将值放到链表头部
            return it->second->second;
        }else{
            return -1;
        }
    }
private:
    int _capacity;
    unordered_map<int,list<pair<int, int>>::iterator> _key_it; //存放键和指向list的迭代器
    list<pair<int,int>> key_val_list; //存放键值对信息
};
void test(){
    

    LRUCache lru(2);
    lru.put(1,1);
    lru.put(2,2);
    cout << lru.get(1) << " ";
    lru.put(3,3);
    cout << lru.get(2) << " ";
    lru.put(4,4);
    cout << lru.get(1) << " ";
    cout << lru.get(3) << " ";
    cout << lru.get(4) << " ";
    //lru.display();
    cout << endl;
}

int main()
{
    

    test ();
    return 0;
}

